1. Field of the Invention
This invention relates generally to memory system for use in data processing equipment and, more particularly, to an apparatus for assigning priority to commands, addresses, and data temporarily stored in a memory controller.
2. Prior Art
Modern data processing systems include various subsystems for performing the functions of manipulating, storing and communicating data. Such a system would include, for example, a central processor, a memory, a plurality of input/output (I/O) devices and a control unit. Such data processing systems may differ significantly in configuration; i.e., various functionalities may be located in different subsystems in accordance with various design criteria. Likewise, the required interface circuitry for communication between the various subsystems may differ both in functionality and operation.
Typically, the central processor manipulates the data in accordance with a series of decodeable instructions called a program. These program instructions are generally retrieved sequentially by the processor and, along with the data which is to be operated upon, are stored in memory devices.
Such memory devices may be of several well known types; however, most commonly used for main memory is a random access device having discrete addressable locations each of which provides storage for a word which may comprise data, and/or commands and may contain specific fields useful in a variety of operations. Generally, when the processor is in need of data or instructions, it will generate a memory cycle and provide an address to the memory in order to retrieve the data or word stored in that address.
The series of instructions comprising the program is usually loaded into memory at the beginning of each operation and occupies a block of memory which noramlly must not be disturbed or altered until a program has been completed. Data to be operated upon by the processor in accordance with the stored instructions is stored in other areas of memory and is retrieved and replaced in accordance with the program instructions.
Communication between the outside world and the data processing system is usually accomplished through the use of a plurality of I/O devices, including such apparatus as magnetic tape handlers, paper tape readers, punch card readers, and remote terminal devices. To control the transfer of information between the I/O devices, an I/O control means is provided which couples the various I/O devices to the processor. The I/O controller coordinates the information flow to and from the various I/O devices and also awards priority when more than one I/O device is attempting to communicate with the rest of the system. Since the I/O devices are usually electromechanical in nature and, as such, are characterized by much slower operating speeds than the remainder of the data processing system, the I/O controller provides buffering to enable the remainder of the processing system to proceed at its normal rate. In many applications, it is advantageous to utilize more than one processor and more than one memory. Likewise, such systems generally require a large number of I/O devices, thus requiring several I/O controllers.
A memory controller is provided to coordinate communications among the processor, memory devices and I/O controllers. It receives requests for access to memory as well as specific requests for communications to other subsystems. The memory controller coordinates the execution of operations and transfers of information and may also provide a means for establishing priority when requests for access to memory are generated by more than one subsystem.
A typical data processing system may contain a single memory controller; however, multiple computer configurations may utilize several memory controllers. In those environments more than one memory controller is employed, each is independent from the other and functions simultaneously, thus providing parallellism in accessing of the memory system. Each memory controller will temporarily store requests from the processors and I/O controllers and generally service these subsystems in accordance with a priority scheme. Data transfers between the various communicating devices and the memory controllers are word oriented, e.g., 40 bits. Typical data processing systems employing memory controllers are shown and described in U.S. Pat. No. 3,413,613, entitled "Reconfigurable Data Processing System".
The instructions, commands, and addresses which are forwarded to the memory controller are accepted and temporarily stored in a stack comprised of a plurality of registers until the appropriate destination units are available to receive the information. Typically, the information so stored was forwarded to the destination units on a First In/First Out basis. A write counter determines which register in the stack received the incoming information, a read counter selects the register whose contents are to be passed on to its destination unit next. The presence of a command in the stack is usually detected by comparing the contents of the write counter with the contents of the read counter. If they are unequal, this indicates that the stack contains information to be passed on. The write counter is advanced when a request is received by the memory controller, and the read counter is advanced when the information is passed from the stack to the appropriate destination unit. If the destination unit corresponding to the next command to be read out of the stack is busy, other commands which occupy a lower position in the stack cannot be forwarded even if their particular destination units are free. Thus, one busy destination unit can effectively block information destined for free units. This is clearly inefficient and accounts for undue delays in a technology where speed is of the utmost importance.
Further, since the stack is a finite length, the danger exists that the write counter will exhaust all available locations in the stack and will wrap around upon itself thus writing new information into a stack location before the contents of that location have been forwarded to its destination unit. If this occurs, the contents of the register or registers in question is lost resulting in a system error.
In order to partially solve these problems, the above referenced copending application describes an apparatus for storing information in the stack. Instructions, commands and addresses are accepted and temporarily stored in the lowest level of the stack not occupied. Associated with each stack level is a busy flip-flop which is set when information is stored in the corresponding stack level. The busy flip-flop is reset when the information is passed on to the destination memory.